package com.fay.basic.proxy;

import java.util.*;

public class TestMomenta {
    public static void main(String[] args) {
        int[] nums = {8, 3, 4, 5, 2, 11, 9};
        //quickSort(nums, 0, nums.length - 1);
        bbSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }

    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
            quickSort(nums, left, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int slow = left;
        int high = right;
        while (slow <= high) {
            while (slow <= high && nums[slow] <= pivot) {
                ++slow;
            }
            while (slow <= high && nums[high] >= pivot) {
                --high;
            }
            if (slow < high) {
                swap(nums, slow, high);
            }
        }
        swap(nums, left, high);
        return high;
    }

    private static void swap(int[] nums, int left, int high) {
        int p = nums[left];
        nums[left] = nums[high];
        nums[high] = p;
    }

    public static void bbSort(int[] nums) {
        if(nums == null || nums.length < 2) return;
        for (int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j + 1] < nums[j]) {
                    flag = false;
                    swap(nums, j, j + 1);
                }
            }
            if (flag) break;
        }
    }
}

class TopK {
    int size;
    PriorityQueue<Integer> priorityQueue;

    public TopK(int k) {
        this.size = k;
        priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
    }

    public void add(int num) {
        if (priorityQueue.size() < size) {
            priorityQueue.offer(num);
        }
        if (num > priorityQueue.peek()) {
            priorityQueue.poll();
            priorityQueue.add(num);
        }
    }

    public List<Integer> getTopK() {
        List<Integer> list = new ArrayList<>(priorityQueue);
        Collections.sort(list);
        return list;
    }
}
